package Lee_code;

import java.util.ArrayList;
import java.util.List;

/**
 * @author blh
 * @date 2024年10月29日 9:16
 * 生成不含相邻零的二进制字符串
 * 给你一个正整数 n。
 * 如果一个二进制字符串 x 的所有长度为 2 的
 * 子字符串
 * 中包含 至少 一个 "1"，则称 x 是一个 有效 字符串。
 * 返回所有长度为 n 的 有效 字符串，可以以任意顺序排列。
 */
public class Lee_3211_1029 {
    List<String> res = new ArrayList<>();

    public List<String> validStrings(int n) {
        // 感觉要用dfs
        dfs(new StringBuilder("0"), n);
        dfs(new StringBuilder("1"), n);
        return res;
    }

    private void dfs(StringBuilder curStr, int n) {
        if (curStr.length() == n) {
            res.add(curStr.toString());
            return;
        }
        // 加一
        curStr.append('1');
        dfs(curStr, n);
        curStr.deleteCharAt(curStr.length() - 1);

        if (curStr.length() > 0 && curStr.charAt(curStr.length() - 1) == '1') {
            // 可以加个0
            curStr.append('0');
            dfs(curStr, n);
            curStr.deleteCharAt(curStr.length() - 1);
        }
    }

    public static void main(String[] args) {
        Lee_3211_1029 method = new Lee_3211_1029();
        System.out.println(method.validStrings(3));
    }
}
